We develop a parallel algorithm for partitioning the vertices of a graph into $p \geq 2$ sets in such a way that few edges connect vertices in different sets. The algorithm is intended for a message-passing multiprocessor system, such as the hypercube, and is based on the Kernighan-Lin algorithm for finding small edge separators on a single processor. We use this parallel partitioning algorithm to find orderings for factoring large sparse symettric positive definite matrices. These orderings not only reduce fill, but also result in good processor utilization and low communication overhead during the factorization. We provide a complexity analysis of the algorithm, as well as some numerical results from an Intel hypercube and a hypercube simulator.
展开▼
机译：我们开发了一种并行算法，用于将图的顶点划分为$ p \ geq 2 $个集合，以使很少的边连接不同集合中的顶点。该算法旨在用于消息传递多处理器系统（例如超立方体），并且基于Kernighan-Lin算法，用于在单个处理器上查找较小的边缘分隔符。我们使用这种并行分区算法来找到分解大型稀疏对称正定矩阵的阶数。这些排序不仅减少了填充，而且在分解期间导致了良好的处理器利用率和较低的通信开销。我们提供了该算法的复杂性分析，以及英特尔超立方体和超立方体模拟器的一些数值结果。
展开▼
